#!/usr/local/bin/ruby
#-*- coding: UTF-8 -*-

require "fac"
class Trans
  include Fac
  @N = 0
  def initialize(n)
    @N = n
  end

  def nextTransOrder(arr,stat)
    maxIndex,maxNum = 0,0
    for i in 0...stat.length do
      if stat[i] == -1 && i != 0 && arr[i] > arr[i-1] && arr[i] > maxNum
        maxNum = arr[i]
        maxIndex = i
      elsif stat[i] == 1 && i != arr.length-1 && arr[i] > arr[i+1] && arr[i] > maxNum
        maxNum = arr[i]
        maxIndex = i
      end
    end

    if maxNum != 0
      if stat[maxIndex] == -1
        arr[maxIndex],arr[maxIndex-1] = arr[maxIndex-1],arr[maxIndex]
        stat[maxIndex],stat[maxIndex-1] = stat[maxIndex-1],stat[maxIndex]
      elsif stat[maxIndex] == 1
        arr[maxIndex],arr[maxIndex+1] = arr[maxIndex+1],arr[maxIndex]
        stat[maxIndex],stat[maxIndex+1] = stat[maxIndex+1],stat[maxIndex]
      end

      (0...arr.length).each do |i|
        if arr[i] > maxNum
          stat[i] = -stat[i]
        end
      end
    end
    return arr,stat
  end

  def transOrder
    arr = Array(1..@N)
    stat = Array.new(@N,-1)

    (0...@N).each do |i|
      print "#{arr[i]}"
    end
    puts

    for i in 1...fac(@N) do
      arr,stat = nextTransOrder(arr,stat)
      (0...arr.length).each { |e|print "#{arr[e]}"  }
      puts
    end
  end
end
